package gold.digger;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC810 {
    public long startExecuteTime = System.currentTimeMillis();


    /*
     * @param 此题目参考了别人代码
     * 这是因为问题情况较为复杂
     * 未来需要再次复习此道题目
     * 题意为，当轮到某玩家时，若此时nums中所有数的异或和为0，则该玩家获胜。
分两种情况：
1. 初始nums中所有数的异或和为0：A直接获胜；
2. 初始nums中所有数的异或和不为0：
a) nums数组初始长度为偶数。若A先拿了一个数剩下的数异或和不为0，现在轮到B拿了。若B拿了一个数后剩余元素的异或和为0，则A胜；若B拿了一个数后剩余数的异或和不为0，则又回到了情况a一开始的时候，如此循环，直到所有数都被拿光了，这样还是A胜。那么是否存在一个所有元素的异或和不为0且数组长度为偶数的数组nums，不论拿走其中哪个数后剩余数的异或和都为0的情况呢？告诉你，不存在！由于nums长度为偶数且异或和不为0，可知nums中存在两个不相等的数x和y，我们令除了x和y的剩余数的异或和为Z。若拿走x后剩余数的异或和为0，即y^Z=0；那么我们就拿走y，由于x!=y，那么x^Z肯定不等于0.也就是说，x和y二者之间肯定存在一个使得拿走它后剩余数的异或和不为0.证毕。
b) nums数组初始长度为奇数。若A拿走一个数后剩余数的异或和为0，则B胜。若A拿走一个数后剩余数的异或和不为0，此时数组中元素个数为偶数个，也就是情况a。根据a中结论，剩余偶数个元素且它们的异或和不为0，而现在是B拿，那么最后肯定B胜了。

综上，若初始nums中所有数的异或和为0，则A直接获胜；否则根据nums数组长度的奇偶性决定，若为奇数则A必败，若为偶数则A必胜。
链接：https://leetcode-cn.com/problems/chalkboard-xor-game/solution/jian-dan-yi-dong-by-hjp6-bzks/
     * 完全是数学思路解法！
     * @return:
     */
    class Solution {
        public boolean xorGame(int[] nums) {
            int n = nums.length, x = 0;
            if (n % 2 == 0) return true;
            for (int num : nums)
                x ^= num;
            return x == 0;
        }
    }


    public void run() {
        Solution solution = new Solution();
        List<Integer> list = new ArrayList<>();
        System.out.println(solution.toString());
    }

    public static void main(String[] args) throws Exception {
        LC810 an = new LC810();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
